package com.wang.utils.sort;

import java.util.Arrays;

/**
 * @author 86173
 * @date 2021/7/30 18:44
 */

/**
 * 基础排序（桶排序） -- 较短的数据前面补0  数据量大，内存不足，耗费额外的内存空间
 * 1、开始设置10个桶 【0~9 十个桶】
 * 	（1）第一轮排序：把每个元素的个位数取出，看应该放在哪个桶（是一个一维数组）中
 * 	（2）按照桶（一维数组）的顺序依次取出数据放入到原数组
 * 2、第二轮
 * 	（1）将每个数的十位取出，依次放入桶中
 * 	（2）按照桶（一维数组）的顺序依次取出数据放入到原数组
 * 3、第三轮
 * 	（1）拿百位，放到桶中
 * 	（2）按照桶（一维数组）的顺序依次取出数据放入到原数组
 * 实际运行的思路
 * 	1、找到最大值--得到最大的数据长度
 * 	2、每一轮每个数据要进行取余  n%i   -- i每一轮会扩大10倍  i*10
 * 	3、每一轮中比较值，放入到桶中
 */

public class RadixSort {


	public int[] sort(int[] sourceArray) throws Exception {
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

		int maxDigit = getMaxDigit(arr);  //maxDigit是位数
		//可以将最大数加空字符串，转换为字符串，获取字符串的长度
		return radixSort(arr, maxDigit);
	}

	/**
	 * 获取最高位数
	 */
	private int getMaxDigit(int[] arr) {
		//最大值，就是位数最多的那个数据
		int maxValue = getMaxValue(arr);
		return getNumLenght(maxValue);
	}

	private int getMaxValue(int[] arr) {
		int maxValue = arr[0];
		for (int value : arr) {
			if (maxValue < value) {
				maxValue = value;
			}
		}
		return maxValue;
	}

	//最大值的位数，长度
	protected int getNumLenght(long num) {
		if (num == 0) {
			return 1;
		}
		int lenght = 0;
		for (long temp = num; temp != 0; temp /= 10) {
			lenght++;
		}
		return lenght;
	}

	private int[] radixSort(int[] arr, int maxDigit) {
		int mod = 10;  //定义初始的桶
		int dev = 1;

		for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
			// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
			//二维数组包含10个一维数组
			//防止的数据溢出
			int[][] counter = new int[mod * 2][0];

			for (int j = 0; j < arr.length; j++) {
				int bucket = ((arr[j] % mod) / dev) + mod;  //每一轮  value % 10  ==> iF（ n>1) value / (n * 10) % 10  不断扩增10倍
				counter[bucket] = arrayAppend(counter[bucket], arr[j]);
			}

			int pos = 0;
			for (int[] bucket : counter) {
				for (int value : bucket) {
					arr[pos++] = value;
				}
			}
		}

		return arr;
	}

	/**
	 * 自动扩容，并保存数据
	 *
	 * @param arr
	 * @param value
	 */
	private int[] arrayAppend(int[] arr, int value) {
		arr = Arrays.copyOf(arr, arr.length + 1);
		arr[arr.length - 1] = value;
		return arr;
	}
}
